\begin{frame}
\frametitle{Extended XMG}

\begin{define}[Ex-XMG \cite{krithivasan1977variations}]
$G = (G_H, G_V)$ is called a Ex-XMG ($X \in \{PS, CS, CF, R\}$) where 
\begin{itemize}
	\item G is a XMG
	\item For each intermediate symbol $S_i \in I$ is attached another symbol d or u (down and up) to determine the direction of vertical derivation. 
\end{itemize}

\end{define}

We write $\Uparrow$ for upwards derivation with reflexiv, transitive closure $\overset{*}{\Uparrow}$

Note: This grammar does not only create rectangular pictures. 

\begin{thm}
$Ex-RML \subsetneq Ex-CFML \subsetneq Ex-CSML \subsetneq Ex-PSML$
\end{thm}

\end{frame}

\begin{frame}
\frametitle{Derivation}

\begin{itemize}
	\item At first, a string $S_{i_1} \dots S_{i_n} \in I^*$ is created.
	\item Let $S_{i_1} \dots S_{i_n} = S_1 \dots S_1 \dots S_1 \dots$. Then derivation is applied on any occurence of $S_1$ with a rule $S_1 \rightarrow a_{1i} A_i$ (downwards or upwards). 
	\item Now derivation continue on $A_i$ until all applied rules are terminal rules. 
	\item Continue with the next intermediate symbol. 
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Example}

\begin{Example}
$M(G) = (L)::(R_1, R_2)$ with attached symbols $(d, u)$. 

\begin{itemize}
	\item $L = \{S_1^nS_2^n \vert n \geq 1\}$
	\item $R_1 = X^+$
	\item $R_2 = .^+$
\end{itemize}

M(G) generates pictures with downwards rectangles of X's on the left side and upward rectangles of .'s. 

\end{Example}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Example derivation}

\[
S
\overset{*}{\Rightarrow}
\boxed{
\begin{aligned}
\begin{matrix}
S_1 & S_1 & S_1 & S_2 & S_2 & S_2
\end{matrix}
\end{aligned}
}
\Downarrow
\boxed{
\begin{aligned}
\begin{matrix}
X & X & X & S_2 & S_2 & S_2 \\[-0.5ex]
S_1 & S_1 & S_1
\end{matrix}
\end{aligned}
}
\]

\[
\overset{*}{\Downarrow}
\boxed{
\begin{aligned}
\begin{matrix}
X & X & X & S_2 & S_2 & S_2 \\[-0.5ex]
X & X & X \\[-0.5ex]
X & X & X \\[-0.5ex]
S_1 & S_1 & S_1
\end{matrix}
\end{aligned}
}
\Downarrow
\boxed{
\begin{aligned}
\begin{matrix}
X & X & X & S_2 & S_2 & S_2 \\[-0.5ex]
X & X & X \\[-0.5ex]
X & X & X \\[-0.5ex]
X & X & X
\end{matrix}
\end{aligned}
}
\]

\[
\Uparrow
\boxed{
\begin{aligned}
\begin{matrix}
 &  &  & S_2 & S_2 & S_2 \\[-0.5ex]
X & X & X & . & . & . \\[-0.5ex]
X & X & X \\[-0.5ex]
X & X & X \\[-0.5ex]
X & X & X
\end{matrix}
\end{aligned}
}
\Uparrow
\boxed{
\begin{aligned}
\begin{matrix}
 &  &  & . & . & . \\[-0.5ex]
X & X & X & . & . & . \\[-0.5ex]
X & X & X \\[-0.5ex]
X & X & X \\[-0.5ex]
X & X & X
\end{matrix}
\end{aligned}
}
\]

\end{frame}